Appendix A contains the following files in one CD-R (of which two identical copies are attached thereto), and is part of the present disclosure and is incorporated by reference herein in its entirety.
Volume in drive D is 021101xe2x80x941847
Volume Serial Number is 966D-05D4
Directory of D: 
11/01/2002 11:00a 96,583 SRCGUI.TXT
11/01/2002 11:00a 290,949 SRCGUT.TXT
2 File(s) 387,532 bytes
Total Files Listed:
2 File(s) 387,532 bytes
0 Dir(s) 0 bytes free
The files of Appendix A form source code of computer programs for an illustrative embodiment of the present invention.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to computer graphics applications.
Photorealism in computer generated graphics has historically tended toward two approaches: one involving modeling three dimensional (3-D) objects, lights, and cameras and performing the computations necessary to simulate the propagation of light, and the other, two dimensional (2-D) paint systems based on digital image acquisition, compositing and retouching. Heretofore, photorealism in two dimensional vector illustration systems has been achieved only by large investments of time by those very skilled in the art. An embodiment of the invention described herein provides a means of rapidly and intuitively creating vector illustrations that approach the representational clarity of 2-D paint and 3-D modeling systems.
The invention of 2-D paint systems is generally attributed to Richard Shoup in 1972 while at Xerox""s Palo Alto Research Center. Commercial paint systems incorporating digital image input and retouching capabilities became available in mid 1980""s with systems such as the Artron Studio Computer from Artronics Inc, South Plainfield N.J. One of the key features of computer paint systems is the ability of a user to manipulate collections of the elements which comprise the image, pixels, with retouching tools that adjust the color components of the pixels, as for example, a darkening tool.
Early solutions to convincing representations of 3-D scene geometry were achieved by Henri Gouraud in xe2x80x9cComputer Display of Curved Surfaces,xe2x80x9d PhD dissertation, University of Utah, Salt Lake City, 1971, and Bui-Thong Phong in xe2x80x9cIllumination for computer generated imagesxe2x80x9d Communications of the ACM, 18:311xe2x80x94317, 1975. These systems included mechanisms for creating 3-D object geometry in the form of parametric surfaces, positioning lights and cameras in a virtual 3-D scene, and modeling the light reflected from the surface toward the camera. These early systems are still remarkable in that they produce fairly convincing results for diffuse surfaces at low computational cost. Two of the key features of these systems are: the ability to define 3-D parametric surfaces as mxc3x97n collections of control vertices, and the ability to render polygonized surfaces with bilinear interpolation of the vertex information.
Since the development of these early systems, ever more detailed renderings have been achieved with a combination of more physically correct modeling techniques and more powerful procedural descriptions of surface detail. One such procedural technique pertinent to this discussion is texture mapping introduced by James Blinn in xe2x80x9cTexture and reflection in computer generated imagesxe2x80x9d Communications of the ACM, 19(10):542xe2x80x94547, 1976. 3. Texture mapping maps locations in a 2-D image to 3-D parametric surface control vertices. This is achieved by normalizing the u,v vertex coordinates by the parametric dimension (m,n) to the unit square. Pixel locations in the source image are similarly normalized by the dimension of the image. The color at a 3-D vertex with a particular normalized coordinate is determined by the pixel value at that same normalized coordinate in the image. The texture coordinates for arbitrary positions on the parametric surface are derived from those at the vertices.
Another technique of setting the color information of 3-D surface vertices is with a 3-D paint program. In a 3-D paint program, the user is not restricted to the plane of an image, but rather positions an object and paint brush in 3-space and deposits paint directly on the 3-D surface. The deposited paint is stored in one or more 2-D images stored as texture maps as discussed in xe2x80x9cDirect WYSIWYG Painting and Texturing on 3D Shapesxe2x80x9d. Computer Graphics (Proc. SIGGRAPH 90), 24(4):215xe2x80x94223, August 1990 by Hanrahan and Haeberli, or alternatively as a level set in an texture octree as in xe2x80x9cOctree Texturesxe2x80x9d ACM Transactions on Graphics (Proc of SIGGRAPH), 21(3):785-790 by Benson and Davis.
One of the primary attractions of vector illustration systems is that they can produce very sharp text and graphics on a printed page. One of the hallmarks of paint and 3-D systems is the ability to represent objects with smooth color transitions and surface detail. Representation of these types of objects in a vector illustration system is generally at odds with the system""s imaging architecture. Illustrations combining sharp text and graphics with smoothly shaded objects predate the use of digitai technology, and are a highly desirable feature of a computer drawing system.
A variety of techniques are employed in vector illustration systems to represent smooth objects, with the three most common techniques being: shape blends, gradients, and gradient meshes. A shape blend is achieved when the color and topology of two shapes are interpolated with a series of in-between objects to create a smooth transition. The smoothness of the transition is dependent on the number of in-between objects. With gradients, a sequence of colors (stops) and their relative separations, along with a transition direction, is established and a single object is shaded with a color ramp that interpolates the stops. Note, that these gradients are generally represented as procedural objects within a page description. When the page description is parsed by a raster image processor for rendering, these procedural objects are expanded in a way very similar to a shape blend with multiple interpolated objects. Both shape blends and gradients are very limited in the types of smooth color transitions that can be represented, thus providing the motivation for the third technique, gradient meshes. Gradient meshes are analogous to parametric surfaces in that they provide an assemblage of control points organized in a normalized u, v coordinate system. In a technique similar to Gouraud shading, the colors at arbitrary positions in a subset of a gradient mesh (a gradient mesh patch) are interpolated from the colors of neighboring control points. Similar to the rendering of surfaces in a 3-D system, a gradient mesh is rasterized at a resolution appropriate for the target output device.
The two existing techniques for establishing the colors at gradient mesh control points are: identifying a subset of control points through a selection and then performing a color edit, and application of a pre-defined color to a mesh control point, or mesh patch. In the case of the application of color to a patch, the edit is performed by storing the pre-defined color at all the control point neighbors defining the patch. These techniques make it quite labor intensive to edit gradient meshes of more than marginal complexity. An embodiment of the invention described herein addresses these inadequacies with a number of new editing techniques, and allows the creation of very complex gradient meshes that achieve the stated goal of photorealism in a fashion that is both intuitive and responsive to a computer artist.
The present invention implements and uses techniques for performing colorization computer graphics operations on an image represented by digital data. The image includes vector objects, and each of the objects is specified by an assemblage of control points each possessing a color. In accordance with different embodiments of the present invention an image sampling utility, a gradient sampling utility, and a mesh painting utility may be used for interactive editing of the image by the user. The image sampling utility, gradient sampling utility, and mesh painting utility, for example, have graphical regions of influence. The colorization function is applied to control points within the extent of the region of influence, whereby when the control points have been colorized, the graphical representation of the vector object is generated.
One embodiment of the present invention includes a computer program product for performing computer graphics operations on an image represented by digital data. The computer program product is tangibly embodied in a computer-readable medium and includes instructions to cause a programmable processor to operate. The instructions cause the processor to receive a representation of a digital image, which includes at least one drawing object organized into a page description. The drawing object includes a gradient mesh that is specified by control points, which have attributes of position on the page description and color. The instructions also cause the processor to receive a user input defining events, wherein each event defines a position on the page description and to calculate an extent of the region of influence over the page description based on at least one defined position. The instructions also cause the processor to recalculate an extent of the region of influence for additional defined events, and perform a colorization function for each control point lying within the recalculated extent of the region of influence, wherein the programmable processor regenerates the gradient mesh specified by the control points after a colorization function is applied to the control points.
In addition, the present invention may include instructions to cause the processor to receive a user input specifying a sampling source. The instructions to perform a colorization function include instructions to obtain color samples at the control point positions from the sampling source, calculate a weighted color combination of the sample color and control point color, and apply the weighted color combination to the control point color.
In addition, the present invention may include instructions to cause the processor to provide an extent profile, the extent profile specifying a fractional coverage value for all positions within the extent of the region of influence and to calculate the fractional coverage value for at the position of each control point lying within the extent of the region of influence for each event. The instructions also cause the processor to calculate a cumulative coverage value associated with each control point based on the accumulation of the fractional coverage values calculated for each control point lying within the extent of the region of influence for each event. In one embodiment, the instructions also cause the processor to attenuate the effect of the colorization function using the cumulative coverage value. In another embodiment the instructions also cause the processor to incorporate the cumulative coverage values into the calculation of the weighted color combination.
Another embodiment of the present invention includes a method for colorizing a gradient mesh. The method includes providing a representation of a digital image comprising at least one drawing object organized into a page description, the drawing object comprising a gradient mesh that is specified by control points, the control points having attributes of position on the page description and color; producing user defined events, wherein each event defines a position on the page description; determining an extent of the region of influence over the page description for colorizing based on at least one defined position; colorizing each control point lying within the extent of the region of influence; determining additional extents of the region of influence for additional defined events; colorizing each control point Iying within the additional extents of the region of influence; and regenerating the gradient mesh specified by the control points after colorizing the control points.
In addition, the method may include providing a sampling source, wherein colorizing includes obtaining color samples from the sampling source at the control point positions; determining a weighted color combination of the sample color and control point color; and applying the weighted color combination to the control point color.
In addition, the method may include specifying a fractional coverage value for all positions within the extent of the region of influence; determining the fractional coverage value for each control point lying within the extent of the region of influence for each event; determining a cumulative coverage value associated with each control point based on the accumulation of the fractional coverage values determined for each control point lying within the extent of the region of influence for each event. In one embodiment, the method includes attenuating the effect of colorizing using the cumulative coverage value. In another embodiment, the method includes incorporating the cumulative coverage values into the calculation of the weighted color combination.
The details of one or more embodiments of the invention are set forth in the accompanying drawing and descriptions below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.